Leetcode 238.除自身以外数组的乘积

题目描述：

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

进阶：你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例:

1
2

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

链接：

https://leetcode-cn.com/problems/product-of-array-except-self

题目分析

  题目中要求我们不使用除法，而实际上使用除法也存在的一定的问题：如果数组中含 0，除以 0 也会出现问题。我们要求的是除了本身以外其余各元素的乘积，而且要达到 $O(n)$ 的时间复杂度，也即前面的乘积结果最好能使用上，怎么使用呢？其实我们要求的结果，可以看做是左边部分的乘积乘上右边部分的乘积。那么先不考虑空间复杂度的问题，我们可以使用两个数组，一个记录从左到右分别乘起来的乘积，一个记录从右到左分别乘起来的乘积，则 result[i] = left[i-1] * right[i+1]。按照这个思路，我们只需要从左到右和从右到左分别遍历一次，得到这两个数组，最后再遍历一次求出各个位置的结果就可以。
  接下来考虑，该如何减小空间复杂度呢？答案数组是不计入所需空间的，我们从左到右的遍历，可以直接记入答案数组中，当然，需要一点小小的变化，第一个数直接记入到第二个空位中，因为第二个结果才需要第一个数的乘积。然后进行从右到左的遍历中，我们只需要使用一个数记录最后的乘积值，作为转移的依据，而乘积结果则可以直接乘入到答案数组中，这样还省去了第三次遍历的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result(nums.size());
        result[0] = 1;
        for(int i = 1; i < nums.size(); i++){
            result[i] = nums[i-1] * result[i-1];
        }
        int R = 1;
        for(int i = nums.size()-1; i >= 0; i--){
            result[i] *= R;
            R *= nums[i];
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们对数组进行了两次遍历。
  空间复杂度：$O(1)$。答案数组不计入空间复杂度中，而我们只需要额外的常数个变量。